package com.yoshino.leetcode.interview150.dynamic;

import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

class Solution {
    public int climbStairs(int n) {
        // f(n) = f(n - 1) + f(n - 2)
        if (n < 3) {
            return n;
        }
        int[] steps = new int[n + 1];
        steps[0] = 1;
        steps[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            steps[i] = steps[i - 1] + steps[i - 2];
        }
        return steps[n];
    }

    public int rob(int[] nums) {
        // f(n) = max[ f(n - 2), f(n - 3)] + nums[n]
        // n - 4 已经被 n - 2选择过
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        if (length == 3) {
            return Math.max(nums[0] + nums[2], nums[1]);
        }
        int[] f = new int[length];
        f[0] = nums[0];
        f[1] = nums[1];
        f[2] = nums[0] + nums[2];
        for (int i = 3; i < length; i++) {
            f[i] = Math.max(f[i - 2], f[i - 3]) + nums[i];
        }
        return Math.max(f[length - 1], f[length - 2]);
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        // memo[i] 表示 s 中索引为 [0, i - 1] 范围的字符串是否可被 wordDict 拆分
        Set<String> collect = wordDict.stream().collect(Collectors.toSet());
        int n = s.length();
        boolean[] memo = new boolean[n + 1];
        memo[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (memo[j] && collect.contains(s.substring(j, i))) {
                    memo[i] = true;
                    break;
                }
            }
        }
        return memo[n];
    }

    public int coinChange(int[] coins, int amount) {
        int[] res = new int[amount + 1];
        Arrays.fill(res, 1, res.length, Integer.MAX_VALUE);
//        for (int i = 1; i <= amount; i++) {
//            for (int coin : coins) {
//                // 10  2
//                if (i >= coin && res[i - coin] != Integer.MAX_VALUE) {
//                    res[i] = Math.min(res[i - coin] + 1, res[i]);
//                }
//            }
//        }
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                if (res[j - coin] != Integer.MAX_VALUE) {
                    res[j] = Math.min(res[j], res[j - coin] + 1);
                }
            }
        }
        return res[amount] == Integer.MAX_VALUE ? -1 : res[amount];
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    res[i] = Math.max(res[i], res[j] + 1);
                }
            }
        }
        // 自身没有算进去
        n = 0;
        for (int r : res) {
            n = Math.max(n, r);
        }
        return n + 1;
    }
}